package LK_Algorithm;

import java.util.*;

public class Alg_Day_6 {
    /*给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
    * 解题思路:滑动窗口-利用双指针来实现*/

    public static int lengthOfLongestSubstring(String s) {
        if(s == null || s.length() == 1){
            return 1;
        }
        int i=0;
        int j=0;
       int count=0;
        HashSet<Character> hashSet=new HashSet<>();
        while (j < s.length()){
            char ch=s.charAt(j);
            /*判断是否存在滑动窗口后移*/
            if (!hashSet.contains(ch)){
                hashSet.add(ch);
                j++;
            }else {
                /*如果存在,收缩滑动窗口*/
                if (count < j-i){
                    count = j-i;
                }
                while (s.charAt(i) != ch){
                    hashSet.remove(s.charAt(i));
                    i++;
                }
                i++;
                j++;
            }
        }
        /*更新最后一次判定值*/
        if (count < j-i){
            count = j-i;
        }
        return count;

    }
    /*给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。
    换句话说，s1 的排列之一是 s2 的 子串 。
    解题思路:滑动窗口-以s1的长度为窗口大小,进行滑动
    由于排列不会改变字符串中每个字符的个数，所以只有当两个字符串每个字符的个数均相等时，一个字符串才是另一个字符串的排列。

*/
        public boolean checkInclusion(String s1, String s2) {
            int n = s1.length(), m = s2.length();
            if (n > m) {
                return false;
            }
            int[] cnt1 = new int[26];
            int[] cnt2 = new int[26];
            for (int i = 0; i < n; ++i) {
                ++cnt1[s1.charAt(i) - 'a'];
                ++cnt2[s2.charAt(i) - 'a'];
            }
            if (Arrays.equals(cnt1, cnt2)) {
                return true;
            }
            for (int i = n; i < m; ++i) {
                ++cnt2[s2.charAt(i) - 'a'];
                --cnt2[s2.charAt(i - n) - 'a'];
                if (Arrays.equals(cnt1, cnt2)) {
                    return true;
                }
            }
            return false;
        }



}
